/*
 * Created on 2006-8-16
 */
package indexing.grid;

import java.awt.Shape;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

import spatial.geometry.*;

/**
 * 
 * A Grid is a two dimensional array of cells.
 * 
 * @uml.property name="grid"
 * @uml.associationEnd multiplicity="(0 -1)"
 */
public class Grid {
	private int size;
	private double cellSize;
	private Cell[][] grid;
	private CellID[] cellIds;

	public Grid(int size, double cellSize) {
		this.cellSize = cellSize;
		this.size = size + 2;
		grid = new Cell[this.size][this.size];
		cellIds = new CellID[this.size * this.size];
		int numids = 0;
		for (int i = 0; i < this.size; i++) {
			for (int j = 0; j < this.size; j++) {
				Location lowerLeft = new Location(i * cellSize, j * cellSize);
				CellID cid = new CellID(i, j);
				cellIds[numids++] = cid;
				grid[i][j] = new Cell(cid, cellSize, lowerLeft);

			}
		}
	}

	/**
	 * Map the given location to the cell in the grid.
	 * 
	 * @param location
	 * @return CellID of the cell where <b>loc</b> locates in.
	 */
	public CellID mapLoc2CellID(Location location) {
		int ix = (int) (location.getX() / this.cellSize);
		int iy = (int) (location.getY() / this.cellSize);
		return new CellID(ix, iy);
	}

	public Cell mapLoc2Cell(Location loc) {
		CellID cid = this.mapLoc2CellID(loc);
		return this.getCell(cid);
	}

	public Collection<CellID> neighboringCells(CellID cellID) {

		Collection<CellID> neighbors = new ArrayList<CellID>();
		int x, y;
		int ix = cellID.getColumn_id();
		int iy = cellID.getRow_id();
		for (x = -1; x < 2; x++)
			for (y = -1; y < 2; y++) {
				CellID c = new CellID(ix + x, iy + y);
				if (this.isValidCell(c) && !c.equals(cellID))
					neighbors.add(c);
			}
		return neighbors;
	}

	/**
	 * get the given cell's neighboring cells in the North, South, East, West
	 * direction.
	 * 
	 * @param cellID
	 * @return
	 */
	public Collection<CellID> neighboringNSEWCells(CellID cellID) {
		Collection<CellID> neighbors = new ArrayList<CellID>();
		CellID north = new CellID(cellID.getColumn_id() + 1, cellID.getRow_id());
		CellID south = new CellID(cellID.getColumn_id() - 1, cellID.getRow_id());
		CellID east = new CellID(cellID.getColumn_id(), cellID.getRow_id() - 1);
		CellID west = new CellID(cellID.getColumn_id(), cellID.getRow_id() + 1);
		if (this.isValidCell(north)) {
			neighbors.add(north);
		}
		if (this.isValidCell(south)) {
			neighbors.add(south);
		}
		if (this.isValidCell(east)) {
			neighbors.add(east);
		}
		if (this.isValidCell(west)) {
			neighbors.add(west);
		}
		return neighbors;
	}

	/**
	 * 
	 * Find the set of cells that intersect with the given shape.
	 * 
	 * @param shape
	 * @return the set of cells that intersect with the given shape. An empty
	 *         set will be returned if the given shape does not intersect with
	 *         any cell.
	 */
	public Set<Cell> intersectedCells(BasicShape shape) {
		/**
		 * <pre>
		 * get the shape's bounds b
		 * get the cell c of the bounds' lower-left corner
		 * rowMin=max(0, c.rowid); colMin=max(0, c.colid)
		 * get the cell c of the bounds' upper-right corner
		 * colMax=min(gridsize-1, c.colID)
		 * rowMax = min(gridsize-1, c.rowID)
		 * 
		 * cellset = empty set
		 * for rowId in [rowMin to rowMax]
		 * 	for colId in [colMin to colMax]
		 * 		if shape.intersects(cell(rowid, colid).rectangle))
		 * 			add to cell set
		 * 		end if
		 * 	end for
		 * end for
		 * 
		 * return cellset
		 * 
		 * </pre>
		 */
		Rectangle rec = shape.getRectBounds();

		CellID lower_left_cid = this.mapLoc2CellID(rec.getLowerLeft());
		int rowMin = Math.max(0, lower_left_cid.getRow_id());
		int colMin = Math.max(0, lower_left_cid.getColumn_id());

		CellID upper_right_cid = this.mapLoc2CellID(rec.getUpperRight());
		int rowMax = Math.min(this.size - 1, upper_right_cid.getRow_id());
		int colMax = Math.min(this.size - 1, upper_right_cid.getColumn_id());

		Set<Cell> cells = new HashSet<Cell>();

		for (int rid = rowMin; rid <= rowMax; rid++) {
			for (int colid = colMin; colid <= colMax; colid++) {
				Cell c = this.getCell(new CellID(colid, rid));
				if (shape.intersects(c)) {
					cells.add(c);
				}
			}
		}

		return cells;
	}

	/**
	 * Find the cells that intersect with the given shape.
	 * 
	 * @param shape
	 * @return
	 */
	public Set<Cell> intersectedCells(Shape shape) {
		Rectangle2D rec = shape.getBounds2D();
		Location lowerLeft = new Location(rec.getMinX(), rec.getMinY());
		Location upperRight = new Location(rec.getMaxX(), rec.getMaxY());

		CellID lower_left_cid = this.mapLoc2CellID(lowerLeft);
		int rowMin = Math.max(0, lower_left_cid.getRow_id());
		int colMin = Math.max(0, lower_left_cid.getColumn_id());

		CellID upper_right_cid = this.mapLoc2CellID(upperRight);
		int rowMax = Math.min(this.size - 1, upper_right_cid.getRow_id());
		int colMax = Math.min(this.size - 1, upper_right_cid.getColumn_id());

		Set<Cell> cells = new HashSet<Cell>();

		for (int rid = rowMin; rid <= rowMax; rid++) {
			for (int colid = colMin; colid <= colMax; colid++) {
				Cell c = this.getCell(new CellID(colid, rid));
				if (shape.intersects(c.getBounds())) {
					cells.add(c);
				}
			}
		}

		return cells;
	}

	/**
	 * ================================== Getters ============================
	 */
	public CellID[] getCellIDs() {
		return cellIds;
	}

	public double getCellSize() {
		return cellSize;
	}

	public int getSize() {
		return size;
	}

	public Cell getCell(CellID cid) {
		if (isValidCell(cid)) {
			return this.grid[cid.getColumn_id()][cid.getRow_id()];
		}
		return null;
	}

	public Cell getCell(int x, int y) {
		/**
		 * Let Q be the cell to be searched. x is the order on x-axis and y is
		 * the order on y-axis. x and y have nothing to do with the real
		 * coordinates. <br>
		 * (x, y) should be inside the rectangle.
		 */
		CellID cid = new CellID(x, y);
		if (isValidCell(cid)) {
			return this.grid[x][y];
		}
		return null;

	}

	public boolean isValidCell(CellID cellID) {
		return ((cellID.getColumn_id() >= 0)
				&& (cellID.getColumn_id() < this.size)
				&& (cellID.getRow_id() >= 0) && (cellID.getRow_id() < this.size));
	}

}
